package main.java.com.itlin.recursion;

public class E05InsertionSort {
    public static void sort(int[] a) {

        insertion(a, 1, a.length - 1);
    }

    public static void insertion(int[] a, int low,int high) {
        if (low == high) return ;

        int t = a[low + 1];

        int i = low ;//已排序区域指针
        while( i >= 1  && a[i] > t){//没找到插入位置
            a[i + 1] = a[i];//空出插入位置
            i--;
        }

        //找到插入位置

        //插入
        a[i + 1] = t;


        insertion(a , low + 1,high);
    }
}
